The widespread use of multicore platforms has produced a growing interest in the design and implementation of concurrent data structures that minimize the use of locks. These data structures (e.g., linked lists, skip lists, B-trees, queues, heaps, and hash maps) typically consist of a collection of nodes linked by pointers. Threads navigate through these links, adding nodes to or removing nodes from the structure. For example, using a so-called “lazy list” algorithm, threads traverse the data structure speculatively, without acquiring locks, then validate the target nodes (using locks or atomic operations) before making changes.
While lock-free navigation is typically more efficient than lock-based navigation, these data structures require more complex memory management because nodes unlinked from the data structure cannot be recycled right away. Instead, after a node is retired, that is, unlinked from the data structure, a grace period must elapse before that memory can be recycled. In managed languages, unused memory is reclaimed automatically by a garbage collector. For languages like C and C++, however, memory management is the explicit responsibility of the programmer.
Current memory reclamation mechanisms for concurrent data structures present an awkward trade-off, where either performance or robustness is sacrificed. For example, epoch-based reclamation performs well when all threads are running on dedicated processors, but the delay or failure of a single thread will prevent any other thread from reclaiming memory. On the other hand, more robust alternatives, such as the hazard pointers technique, are expensive because they require additional memory barriers. For example, on mainstream multicore architectures with a total-store ordering (TSO) memory model, the hazard pointer technique requires a store-load barrier after every store to a hazard pointer.